package BFS;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-12
 * Time:16:40
 * Text：542. 01 矩阵
 */
public class Texts5 {
    int[][] cMat;
    int m,n;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};

    public void bfs(Queue<int[]> q,int[][] mat){
        int ret=0;
        while(!q.isEmpty()){
            int k=q.size();
            ret++;
            while(k-->0){
                int[] array=q.poll();
                for(int i=0;i<4;i++){
                    int x=array[0]+dx[i],y=array[1]+dy[i];
                    if(x>=0 && x<m && y>=0 && y<n && cMat[x][y]==0 && mat[x][y]!=0){
                        cMat[x][y]=ret;
                        q.add(new int[]{x,y});
                    }
                }
            }
        }
    }
    public int[][] updateMatrix(int[][] mat) {
        Queue<int[]> q=new LinkedList<>();
        m = mat.length;
        n = mat[0].length;
        cMat = new int[m][n];
        for(int i=0;i< mat.length; i++){
            for(int j = 0; j < n; j++){
                if(mat[i][j]==0){
                    q.add(new int[]{i,j});
                }
            }
        }
        bfs(q,mat);
        return cMat;
    }

    public static void main(String[] args) {
        int[][] array={{0,0,0},{0,1,0},{0,0,0}};
        Texts5 t1=new Texts5();
        t1.updateMatrix(array);
    }
}
